COMMENT ⊗   VALID 00008 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	% This program by D. E. Knuth is not copyrighted and can be used freely.
C00004 00003	@* Introduction.
C00011 00004	@* The character set.
C00016 00005	@* Inputting the data.
C00019 00006	@* Pixel compensation.
C00028 00007	@* The main program.
C00029 00008	@* Index.
C00040 ENDMK
C⊗;
% This program by D. E. Knuth is not copyrighted and can be used freely.

% Here is TeX material that gets inserted after \input webmac
\def\title{HALFTONES}
\font\mc=cmr9

\def\con{\par\vfill\eject % finish the section names
  \rightskip 0pt \hyphenpenalty 50 \tolerance 200
  \setpage
  \output{\normaloutput\page\lheader\rheader}
  \titletrue % prepare to output the table of contents
  \pageno=\contentspagenumber \def\rhead{TABLE OF CONTENTS}
  \message{Table of contents:}
  \topofcontents
  \line{{\bf Sample}\hfil Section}
  \def\Z##1##2##3{\line{\ignorespaces##1
    \leaders\hbox to .5em{.\hfil}\hfil\hbox to2em{\hss##2}}}
  \readcontents\relax % read the contents info
  \botofcontents \end} % print the contents page(s) and terminate
@* Introduction.
This program prepares 33-level halftone images for use in \TeX\ files. The
input is assumed to be a sequence of pictures expressed in the form
$$\halign{\qquad#\hfil\cr
$m\quad n$\cr
$\langle\,$first line of pixel data, $n$ characters long$\,\rangle$\cr
\ \ \ \dots\cr
$\langle\,m$th line of pixel data, $n$ characters long$\,\rangle$\cr}$$
terminated by a line that says simply `\.0'.
The pixel data consists of the characters |"0"| to~|"9"| and
|"A"| to~|"V"|, representing 32 levels of darkness from black to white.
[This convention was adopted from the appendix to {\sl Digital Image
Processing\/} by Gonzalez and Wintz (Addison-Wesley, 1977).]
@↑Gonzalez, Rafael C.@>
@↑Wintz, Paul@>

The output is the same set of pictures, expressed in a simple format used
for 33-level halftones, with ASCII characters |"0"| to |"P"| representing
darkness levels from white to black. The levels are adjusted to compensate
for the idiosyncrasies of Canon {\mc LBP-CX} laser-printing engines.
Two dots are typeset for each pixel of input; hence there are $2m$
``half\/lines'' of $n$-character data in the output.

@ Here's an outline of the entire Pascal program:

@p program halftones(@!input,@!output);
label @<Labels in the outer block@>@/
const @<Constants in the outer block@>@/
type @<Types in the outer block@>@/
var@?@<Global variables@>@/
@#
procedure initialize; {this procedure gets things started properly}
	var@?@<Local variables for initialization@>@/
	begin @<Set initial values@>@;
	end;@#
begin initialize; @<The main program@>;
end.

@ Each picture in the input data must contain fewer than |max_m| rows and
|max_n| columns.

@<Constants in the outer block@>=
@!max_m=200; {$m$ should be less than this}
@!max_n=200; {$n$ should be less than this}

@ The main program has one statement label, namely |cleanup_and_terminate|.

@d cleanup_and_terminate=9998
@d finish==goto cleanup_and_terminate
 {do this when all the pictures have been output}

@<Labels in...@>=cleanup_and_terminate;
@* The character set.
We need translation tables between ASCII and the actual character
set, in order to make this program portable. The standard conventions of
{\sl \TeX: The Program\/} are copied here, essentially verbatim.

@d text_char == char {the data type of characters in text files}
@d first_text_char=0 {ordinal number of the smallest element of |text_char|}
@d last_text_char=127 {ordinal number of the largest element of |text_char|}

@<Types...@>=
@!ASCII_code=0..127; {seven-bit numbers}

@ @<Glob...@>=
@!xord: array [text_char] of ASCII_code;
	{specifies conversion of input characters}
@!xchr: array [ASCII_code] of text_char;
	{specifies conversion of output characters}

@ @<Set init...@>=
xchr[@'40]←' ';
xchr[@'41]←'!';
xchr[@'42]←'"';
xchr[@'43]←'#';
xchr[@'44]←'$';
xchr[@'45]←'%';
xchr[@'46]←'&';
xchr[@'47]←'''';@/
xchr[@'50]←'(';
xchr[@'51]←')';
xchr[@'52]←'*';
xchr[@'53]←'+';
xchr[@'54]←',';
xchr[@'55]←'-';
xchr[@'56]←'.';
xchr[@'57]←'/';@/
xchr[@'60]←'0';
xchr[@'61]←'1';
xchr[@'62]←'2';
xchr[@'63]←'3';
xchr[@'64]←'4';
xchr[@'65]←'5';
xchr[@'66]←'6';
xchr[@'67]←'7';@/
xchr[@'70]←'8';
xchr[@'71]←'9';
xchr[@'72]←':';
xchr[@'73]←';';
xchr[@'74]←'<';
xchr[@'75]←'=';
xchr[@'76]←'>';
xchr[@'77]←'?';@/
xchr[@'100]←'@@';
xchr[@'101]←'A';
xchr[@'102]←'B';
xchr[@'103]←'C';
xchr[@'104]←'D';
xchr[@'105]←'E';
xchr[@'106]←'F';
xchr[@'107]←'G';@/
xchr[@'110]←'H';
xchr[@'111]←'I';
xchr[@'112]←'J';
xchr[@'113]←'K';
xchr[@'114]←'L';
xchr[@'115]←'M';
xchr[@'116]←'N';
xchr[@'117]←'O';@/
xchr[@'120]←'P';
xchr[@'121]←'Q';
xchr[@'122]←'R';
xchr[@'123]←'S';
xchr[@'124]←'T';
xchr[@'125]←'U';
xchr[@'126]←'V';
xchr[@'127]←'W';@/
xchr[@'130]←'X';
xchr[@'131]←'Y';
xchr[@'132]←'Z';
xchr[@'133]←'[';
xchr[@'134]←'\';
xchr[@'135]←']';
xchr[@'136]←'↑';
xchr[@'137]←'_';@/
xchr[@'140]←'`';
xchr[@'141]←'a';
xchr[@'142]←'b';
xchr[@'143]←'c';
xchr[@'144]←'d';
xchr[@'145]←'e';
xchr[@'146]←'f';
xchr[@'147]←'g';@/
xchr[@'150]←'h';
xchr[@'151]←'i';
xchr[@'152]←'j';
xchr[@'153]←'k';
xchr[@'154]←'l';
xchr[@'155]←'m';
xchr[@'156]←'n';
xchr[@'157]←'o';@/
xchr[@'160]←'p';
xchr[@'161]←'q';
xchr[@'162]←'r';
xchr[@'163]←'s';
xchr[@'164]←'t';
xchr[@'165]←'u';
xchr[@'166]←'v';
xchr[@'167]←'w';@/
xchr[@'170]←'x';
xchr[@'171]←'y';
xchr[@'172]←'z';
xchr[@'173]←'{';
xchr[@'174]←'|';
xchr[@'175]←'}';
xchr[@'176]←'~';@/
xchr[0]←' '; xchr[@'177]←' ';
	{ASCII codes 0 and |@'177| do not appear in text}

@ @<Local variables for init...@>=
i:0..last_text_char;

@ @<Set init...@>=
for i←1 to @'37 do xchr[i]←' ';
for i←first_text_char to last_text_char do xord[chr(i)]←@'177;
for i←1 to @'176 do xord[xchr[i]]←i;
@* Inputting the data.
We keep the pixel values in a big global array called |v|.
The variables |m| and~|n| keep track of the current number of rows
and columns in use.

The |dd| table contains density values assumed for the input,
indexed by single-character codes.

@<Glob...@>=
@!v:array [0..max_m,0..max_n] of real; {pixel darknesses, from 0.0 to 1.0}
@!m:integer; {rows |0..m+1| of |v| should contain relevant data}
@!n:integer; {columns |0..n+1| of |v| should contain relevant data}
@!dd:array[text_char] of real;

@ All input codes give zero density, except |"0"| to~|"9"| and
|"A"| to |"V"|.

@<Set init...@>=
for i←first_text_char to last_text_char do dd[chr(i)]←0.0;
for i←"0" to "9" do dd[chr(i)]←1.0-(i-"0")/31.0;
for i←"A" to "V" do dd[chr(i)]←1.0-(i-"A"+10)/31.0;

@ The process of inputting pixel values is quite simple. We terminate the
program if anomalous values of |m| and~|n| occur. Boundary values are added
at the top, left, right, and bottom in order to provide ``padding'' that
will be convenient in the pixel transformation process. Each boundary value
is equal to one of its adjacent neighbors.

@<Input a picture, or terminate the program@>=
read(m);@+if (m≤0)∨(m≥max_m) then finish;
read_ln(n);@+if (n≤0)∨(n≥max_n) then finish;
for i:=1 to m do
	begin for j:=1 to n do
		begin read(c); v[i,j]:=dd[c];
		end;
	v[i,0]:=v[i,1]; v[i,n+1]:=v[i,n];@/
	read_ln;
	end;
for j:=0 to n+1 do
	begin v[0,j]:=v[1,j]; v[m+1,j]:=v[m,j];
	end

@ The code just written makes use of three temporary registers that must
be declared:

@<Glob...@>=
@!i,@!j:integer; {current row and column}
@!c:char; {character read from input}
@* Pixel compensation.
The 33-level output of this program is assumed to be printed by a font
that contains $4\times8$ characters, where each character has 0 to~32
black bits. Physical properties of output devices cause distortions,
so that a character with |k| black bits does not have an apparent
density of |k/32|. We therefore maintain a table of apparent density
values.

@d max_l=32 {maximum output level}

@<Glob...@>=
@!d:array[0..max_l] of real; {apparent densities, from 0.0 to 1.0}

@ This table is based on some densitometer measurements that are not
especially reliable. The amount of toner seems to vary between the top of
a page and the bottom; also blocks of the character |"N"| seem to appear
darker than blocks of the character |"O"|, because of some property of
xerography, although the |"O"| has one more bit turned on. Such
anomalies have been smoothed out here, since the resulting values should
prove good enough in practice.

@<Set init...@>=
d[0]:=0.0;
d[1]:=0.06;
d[2]:=0.095;
d[3]:=0.125;
d[4]:=0.155;@/
d[5]:=0.175;
d[6]:=0.215;
d[7]:=0.245;
d[8]:=0.27;
d[9]:=0.29;@/
d[10]:=0.3;
d[11]:=0.31;
d[12]:=0.32;
d[13]:=0.33;
d[14]:=0.34;@/
d[15]:=0.35;
d[16]:=0.36;
d[17]:=0.37;
d[18]:=0.38;
d[19]:=0.4;@/
d[20]:=0.42;
d[21]:=0.44;
d[22]:=0.47;
d[23]:=0.5;
d[24]:=0.53;@/
d[25]:=0.57;
d[26]:=0.61;
d[27]:=0.66;
d[28]:=0.72;
d[29]:=0.80;@/
d[30]:=0.88;
d[31]:=0.96;
d[32]:=1.0;

@ We convert the pixel values by using a variant of the Floyd-Steinberg
algorithm for adaptive grayscale [Society for Information Display,
{\sl SID 75 Digest}, 36--37].
@↑Floyd, Robert W@>
@↑Steinberg, Louis@>
The idea is to find the best available density, then to diffuse the error
into adjacent pixels that haven't yet been processed.

The following code assumes that |x| is the desired density value
in column~|j| of the current half\/line.
It outputs one 33-level density,
then updates |x| and~|j| in preparation for the next column.
Adjustments to the densities in the two next half\/lines are
accumulated in auxiliary arrays |next1| and |next2|; this will compensate
for errors in the current half\/line.

We assume that |next1[j]|, |next1[j+1]|, and |next2[j]| correspond to the
dots that are adjacent to |current[j]|.

@<Output one value and move to the next column@>=
@<Find |l| so that |d[l]| is as close as possible to |x|@>;
write(xchr["0"+l]); err←x-d[l];@/
next1[j]:=next1[j]+alpha*err;@/
next2[j]:=beta*err;@/
j←j+1; {move right}
next1[j]:=next1[j]+gamma*err;@/
x:=current[j]+delta*err

@ The constants |alpha..delta| control the distribution of errors to
adjacent dot positions.

@<Set init...@>=
alpha:=7/16; {error diffusion to SW neighbor}
beta:=1/16; {error diffusion to S neighbor}
gamma:=5/16; {error diffusion to SE neighbor}
delta:=3/16; {error diffusion to E neighbor}

@ Here is the overall control of the process.
Every half\/line of the picture being output is a sequence of ASCII characters
from |"0"| to |"P"|, terminated by |"."|.

@<Output the picture@>=
for j:=1 to n+1 do
	begin next1[j]:=0.0; next2[j]:=0.0;
	end;
for i:=1 to m div 2 do
	begin @<Set the current half\/line data for the upper row of dots in line~|i|@>;
	j:=1; x:=current[1];
	repeat @<Output one value...@>;
	until j>n;
	write_ln('.');
	@<Set the current half\/line data for the lower row of dots in line~|i|@>;
	j:=1; x:=current[1];
	repeat @<Output one value...@>;
	until j>n;
	write_ln('.');
	end

@ The density value for dot |j| in the upper half\/line of line~|i| is obtained
as a weighted average of the input values in rows |i-1| and~|i|, columns
|j| and~|j+1|. The upper half\/line is skewed to the right, so we must shift
|next1| and |next2| appropriately.

@<Set the current half\/line data for the upper row of dots in line~|i|@>=
for j←1 to n do
	begin current[j]←v[2*i-1,j]+next1[j+1];
	next1[j]←next2[j];
	end;
next1[n+1]←0.0

@ The lower half\/line is similar, but in this case there is leftward skew;
we use rows |i| and~|i+1|, columns |j-1| and~|j|.

@<Set the current half\/line data for the lower row of dots in line~|i|@>=
for j←1 to n do
	begin current[j]←v[2*i,j]+next1[j];
	next1[j+1]←next2[j];
	end;
next1[1]←0.0

@ The algorithm is now complete except for the part that chooses the
closest possible dot size. A straightforward binary search works well
for this purpose:

@<Find |l| so that |d[l]| is as close as possible to |x|@>=
if x≤0.0 then l←0
else if x≥1.0 then l←max_l
else	begin low_l←0; high_l←max_l; {we have |d[low_l]≤x<d[high_l]|}
	while high_l-low_l>1 do
		begin mid_l:=(low_l+high_l) div 2;
		if x≥d[mid_l] then low_l:=mid_l
		else high_l:=mid_l;
		end;
	if x-d[low_l]≤d[high_l]-x then l←low_l@+else l←high_l;
	end

@ We had better declare the variables we've been using.

@<Glob...@>=
@!x:real; {current pixel density}
@!err:real; {difference between |x| and the best we can achieve}
@!current:array[0..max_n] of real; {desired densities in current half\/line}
@!next1,@!next2:array[0..max_n] of real; {corrections to subsequnt densities}
@!alpha,@!beta,@!gamma,@!delta:real; {constants of error diffusion}
@!l,@!low_l,@!mid_l,@!high_l:0..max_l; {trial density levels}
@* The main program.
Now we're ready to put all the pieces together.

@<The main program@>=
write_ln('\input hf33'); write_ln;
while true do
	begin @<Input a picture...@>;
	write_ln('\beginhalftone');
	@<Output the pic...@>;
	write_ln('\endhalftone'); write_ln;
	end;
cleanup_and_terminate:
@* Index.
Here are the quantities declared and/or used in the program.
(The uses of single-letter variables aren't indexed.)